這是什麼鬼？

在昨天提到，Array 會一次跟記憶體要求一個區塊，那會不會有一種可能，記憶體因為各種變數索取記憶空間，造成區塊之間存在不少未被使用的區塊？答案是肯定的，這些未被使用的區塊十分可惜，人們因此思考該如何運用這些區塊？因此誕生 Linked List，為的就是解決這個問題。

此外，因為 C 的 Array 的長度在宣告時就決定好，之後無法修改。因此 Linked List 同時也解決這個問題。

以 JS 的角度來看，Linked List 解決的兩個問題，對 JS 沒有任何影響，那還需要學習嗎？答案是肯定的，之後的資料結構 Tree 需要相關的知識。

C 如何運用 Linked List

Linked List 能夠順利成真的關鍵原因在於 指標（Pointer），簡單來說，C 允許得到變數的記憶體位置，可以在一個節點上記錄該節點的值與指向哪一個節點的記憶體位置，來做出 Linked List。

#include <stdio.h>

struct Node
{
    int val;
    struct Node *next;
};

// 新節點放在第一個位置
void push(struct Node **head_ref, int new_val)
{
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->val = new_val;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// 插入在中間節點
void insertAfter(struct Node *prev_node, int new_val)
{
    if (prev_node == NULL)
    {
        printf("prev_node 不得為 NULL");
        return;
    }

    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->val = new_val;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

// 新節點放在最後一個位置
void append(struct Node **head_ref, int new_val)
{
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    struct Node *last_node = *head_ref;
    new_node->val = new_val;
    new_node->next = NULL;

    // 如果 Linked List 是存在，則建立一個
    if (*head_ref == NULL)
    {
        *head_ref = new_node;
        return;
    }

    // 找尋目前最後一個節點
    while (last_node->next != NULL)
    {
        last_node = last_node->next;
    }

    last_node->next = new_node;
    return;
}

// 刪除節點
void deleteNode(struct Node **head_ref, int target_val)
{
    struct Node *temp = *head_ref, *prev_node;

    // 刪除第一個節點
    if (temp != NULL && temp->val == target_val)
    {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    // 找尋目標節點
    while (temp != NULL && temp->val != target_val)
    {
        prev_node = temp;
        temp = temp->next;
    }

    // 沒找到目標節點
    if (temp == NULL)
    {
        return;
    }

    // 找到目標節點，將其移除
    prev_node->next = temp->next;

    free(temp);
}

來源：

• Linked List | Set 2 (Inserting a node)
• Linked List | Set 3 (Deleting a node)

如何實作在 JS & Java？

簡單來說，使用 Object 或是 Class 即可模仿出，先定義好 Node 後再拼裝出 Linked List。

JS

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }

}

class LinkedList {
  constructor() {
    this.firstNode = null;
    this.lastNode = null;
  }

  isEmpty() {
    return this.firstNode == null;
  }

  insert(newNode) {
    if (this.isEmpty()) {
      this.firstNode = newNode;
      this.lastNode = newNode;
    } else if (newNode.next === this.firstNode) {
      // 新節點放在第一個位置
      newNode.next = this.firstNode;
      this.firstNode = newNode;
    } else if (newNode.next === null) {
      // 新節點放在最後一個位置
      this.lastNode.next = newNode;
      this.lastNode = newNode;
    } else {
      // 插入在中間節點
      let targetNode = this.firstNode;
      let beforeTargetNode = this.firstNode;

      while (newNode.newNode !== targetNode.next) {
        beforeTargetNode = targetNode;
        targetNode = targetNode.next;
      }

      beforeTargetNode.next = newNode;
      newNode.next = targetNode;
    }
  }

  delete(deleteNode) {
    let targetNode, beforeTargetNode;

    if (this.firstNode.val === deleteNode.val) {
      // 刪除第一個節點
      this.firstNode = this.firstNode.next;
    } else if (this.lastNode.val === deleteNode.val) {
      // 因為 Linked List 是單行道，所以要從頭一個一個找尋，最後第二個節點
      targetNode = this.firstNode;

      while (targetNode.next !== this.lastNode) {
        targetNode = targetNode.next;
      }

      targetNode.next = this.lastNode.next;
      this.lastNode = targetNode;
    } else {
      // 刪除中間的節點
      targetNode = this.firstNode;
      beforeTargetNode = this.firstNode;

      while (targetNode.val !== deleteNode.val) {
        beforeTargetNode = targetNode;
        targetNode = targetNode.next;
      }

      beforeTargetNode.next = deleteNode.next;
    }
  }

}

Java

class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {
    private Node firstNode;
    private Node lastNode;

    public boolean isEmpty() {
        return firstNode == null;
    }

    public void insert(Node newNode) {
        if (this.isEmpty()) {
            firstNode = newNode;
            lastNode = newNode;
        } else if (newNode.next == firstNode) {
            // 新節點放在第一個位置
            newNode.next = firstNode;
            firstNode = newNode;
        } else if (newNode.next == null) {
            // 新節點放在最後一個位置
            lastNode.next = newNode;
            lastNode = newNode;
        } else {
            // 插入在中間節點
            Node targetNode = firstNode;
            Node beforeTargetNode = firstNode;

            while (newNode.next != targetNode.next) {
                beforeTargetNode = targetNode;
                targetNode = targetNode.next;
            }

            beforeTargetNode.next = newNode;
            newNode.next = targetNode;
        }
    }

    public void delete(Node deleteNode) {
        Node targetNode;
        Node beforeTargetNode;

        if (firstNode.val == deleteNode.val) {
            // 刪除第一個節點
            firstNode = firstNode.next;
        } else if (lastNode.val == deleteNode.val) {
            // 因為 Linked List 是單行道，所以要從頭一個一個找尋，最後第二個節點
            targetNode = firstNode;

            while (targetNode.next != lastNode) {
                targetNode = targetNode.next;
            }

            targetNode.next = lastNode.next;
            lastNode = targetNode;
        } else {
            // 刪除中間的節點
            targetNode = firstNode;
            beforeTargetNode = firstNode;

            while (targetNode.val != deleteNode.val) {
                beforeTargetNode = targetNode;
                targetNode = targetNode.next;
            }

            beforeTargetNode.next = deleteNode.next;
        }
    }
}

常見類型

以上示範稱為 Singly Linked List，只知道下一個節點的位置。除此之外，還有其他種類：

• Circular Linked List，最後一個節點的 Next 指向第一個節點，形成一個循環 Linked List。
• Doubly Linked List，除了知道下一個節點的位置，也知道上一個節點的，代價就是要多花記憶體空間來記住。

刷題：2. Add Two Numbers

題目

連結

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思考

觀察 Example 可以得知，就是常見的加法，加法的順序改成從左至右，而不是從右至左。接下來要思考的是，如何操作 Linked List？要考量的點是：

• 依序進行相加，如果相加結果大於 10，那要模擬進位，結果要減掉 10，下一組的結果要加 1。
• 有可能兩組 List 的長度不同，所以要考量，此時只能操作其中一組。
• 為了方便操作，會先製作一個負責當開頭的節點，目的是方便操作。

解題

JS

const addTwoNumbers = (l1, l2) => {
  let headNode = new ListNode(0);
  let temp = headNode;
  let sum = 0, carry = 0;

  while (l1 !== null || l2 !== null || sum > 0) {
    if (l1 !== null) {
      sum += l1.val;
      l1 = l1.next;
    }

    if (l2 !== null) {
      sum += l2.val;
      l2 = l2.next;
    }

    if (sum >= 10) {
      carry = 1;
      sum = sum - 10;
    }

    temp.next = new ListNode(sum);
    temp = temp.next;
    sum = carry;
    carry = 0;
  }

  return headNode.next;
};

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode headNode = new ListNode(0);
        ListNode temp = headNode;
        int sum = 0, carry = 0;

        while (l1 != null || l2 != null || sum > 0) {
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            if (sum >= 10) {
                carry = 1;
                sum -= 10;
            }

            temp.next = new ListNode(sum);
            temp = temp.next;
            sum = carry;
            carry = 0;
        }

        return headNode.next;
    }
}

C

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *head_node;
    struct ListNode *temp_node;
    int overflow = 0;
    int sum = 0, l1Val, l2Val;

    head_node = (struct ListNode *)malloc(sizeof(struct ListNode));
    temp_node = head_node;

    while (l1 != NULL || l2 != NULL)
    {
        l1Val = (l1 ? l1->val : 0);
        l2Val = (l2 ? l2->val : 0);
        sum = l1Val + l2Val + overflow;
        overflow = sum / 10;
        temp_node->val = (sum > 9) ? (sum % 10) : sum;

        l1 = (l1) ? l1->next : NULL;
        l2 = (l2) ? l2->next : NULL;

        if (l1 != NULL || l2 != NULL)
        {
            temp_node->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            temp_node = temp_node->next;
        }
        else if (overflow)
        {
            temp_node->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            temp_node = temp_node->next;
            temp_node->val = overflow;
            break;
        }
    }

    temp_node->next = NULL;
    return head_node;
}

看法

明顯地，JS 與 Java 又一次寫出同樣內容的答案，畢竟這兩個語言相似的地方較多。C 則是完全不同的世界，要宣告 node 時同時配置記憶體，其餘部分倒是蠻相近的。

結論

這篇與其說是寫給其他人看，倒不如說是寫給我自己看，過往聽過 Linked List，覺得就是 JS 的物件操作，實際用 C 來跑，才發現有些許的不同。

其實我已經開始期待後面介紹 Tree 的時候了。